Quantum Computing. Research on what is now called quantum computing traces to at least as far back as R. Feynman, see Feynman, 1982, International Journal of Theoretical Physics 21, pp. 467-488, which is hereby incorporated by reference in its entirety. Feynman noted that quantum systems are inherently difficult to simulate with conventional computers but that observing the evolution of an analogous quantum system could provide an exponentially faster way to solve the mathematical model of a system. In particular, solving a model for the behavior of a quantum system commonly involves solving a differential equation related to the Hamiltonian of the quantum system. David Deutsch observed that a quantum system could be used to yield a time saving, later shown to include exponential time savings, in certain computations. If one had a problem, modeled in the form of an equation that is analogous to the Hamiltonian of the quantum system, the behavior of the system could provide information regarding the solutions to the equation. See Deutsch, 1985, Proceedings of the Royal Society of London A 400, pp. 97-117, which is hereby incorporated by reference in its entirety.
Several solid state embodiments have been proposed for scalable quantum computers. These include superconducting qubits comprised of superconducting material and Josephson junctions. One such proposal was published in 1997. See Bocko et al., 1997, IEEE Transactions of Applied Superconductivity 7, pp. 3638-3641, which is hereby incorporated by reference in its entirety. Since that time, many superconducting qubits have been disclosed. For a review of the field see Makhlin et al., 2002, Reviews of Modern Physics 73, pp. 357-400, which is hereby incorporated by reference in its entirety.
Additional solid state quantum computers include those based on coupled spin systems. These proposals include coupled quantum dots. See, for example, Loss and DiVincenzo, 1998, Physical Review A 57, pp. 120-126, which is hereby incorporated by reference in its entirety. An additional example of a coupled spin system is donor atoms with non zero nuclear spin, e.g. P31, implanted in homogenous arrays zero nuclear spin silicon, see U.S. Pat. No. 6,472,681, which is hereby incorporated by reference in its entirety.
Qubits. A qubit is the fundamental building block of a quantum computer. The qubit has two basis states, which are often labeled |0 and |1. Notation like ‘|’ is called Dirac notation, and it is the standard notation for states in quantum mechanics. See, for example, Nielsen & Chuang, 2000, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge. The similarities between these quantum basis states and the binary 0 and 1 states make these quantum states promising candidates for purposes of computation. The difference between bits and qubits is that a qubit can be in a state other that |0 or |1. It is also possible to form linear combinations of states, often called superpositions:|ψ=α|0+β|1The numbers α and β are complex numbers, where |α|2+|β|2=1. Put another way, the state of a qubit is a vector in a two-dimensional complex vector space. The special states |0 and |1 are known as computational basis states, and form an orthonormal basis for this vector space. A qubit is capable of evolving from one state to another state in a quantum mechanical manner. As mentioned before, a qubit can be in a superposition of both basis states. In simplified terms, this can be described as the qubit being in both quantum basis states a once. For more information on qubits, see DiVincenzo in Braunstein and Lo (eds.), 2001, Scalable quantum computers, Wiley-VCH, New York.
A classical bit can be examined to determine whether it is in the state 0 or 1. For example, classical computers do this all the time when they retrieve the contents of their memory. In contrast, a qubit cannot be directly examined to determine its quantum state, that is, the values α and β. However, because qubits adhere to the laws of quantum mechanics, when a qubit is measured it reverts to a classical state. The measurement can be either the result 0, with probability |α|2, or the result 1, with probability |β|2. Further as |α|2+|β|2=1, the probabilities must sum to one. Geometrically, this can be interpreted as the condition that the qubit's state be normalized to length 1. Thus, in general a qubit's state is a unit vector in a two-dimensional complex vector space. One representation of such a space is a Bloch sphere. See, for example, Nielsen and Chuang, 2000, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge.
Single qubit terms. Classical computer circuits consist of wires and logic gates. The wires are used to carry information around the circuit, while the logic gates perform manipulations of the information, converting it from one form to another. Consider, for example, classical single bit logic gates. The only non-trivial member of this class is the NOT gate, whose operation is defined by its truth table, in which 0→1 and 1→0, that is, the 0 and 1 states are interchanged. By comparison, the quantum NOT gate acts linearly to take the stateα|0+β|1to the corresponding state in which the role of |0 and |1 have been interchanged,α|1+β|0.
There is a convenient way of representing the quantum NOT gate in matrix form, which follows directly from the linearity of quantum gates. Suppose a matrix σX is defined to represent the quantum NOT gate as follows:
      σ    X    ≡      (                            0                          1                                      1                          0                      )  (The notation σX for the quantum NOT gate is used for historical reasons). The quantum state α|0+β|1 of a qubit can be written in a vector notation as:
      [                            α                                      β                      ]    ,with the top entry corresponding to the probability amplitude for |0 and the bottom entry the probability amplitude for |1. Then, the corresponding output from the quantum NOT gate is
            σ      X        ⁡          [                                    α                                                β                              ]        =            [                                    β                                                α                              ]        .  
As the above example indicates, single qubit quantum gates can be described by two by two matrices, subject to the limitation that the matrix representing the gate is unitary. Thus, if U is a matrix describing a single qubit gate, the condition U†U=I, where U† is the adjoint of U (obtained by transposing and then complex conjugating U), and I is the two by two identity matrix. The single qubit gate σX is one of the Pauli matrices. In fact, each of the three Pauli matrices serve as a unique single-qubit gate. The other Pauli matrices (operators) are:
                              σ          Y                =                  (                                                    0                                                              -                  i                                                                                    i                                            0                                              )                                                  σ          Z                =                  (                                                    1                                            0                                                                    0                                                              -                  1                                                              )                    
Two by two matrices are not the only way to represent single qubit quantum operations. One can also use creation and annihilation operators. Creation and annihilation operators are described more fully in the example section below. For more information on creation and annihilation operators, see Sakurai and Tuan, 1994, Modern Quantum Mechanics Revised Edition, Addison-Wesley Publishing Company, which is hereby incorporated by reference in its entirety.
Two qubit terms. In most quantum computing system designs, qubits are coupled together, often pair-wise. The functions of such pair-wise couplings include facilitating the entanglement of the quantum basis states of the coupled qubits. Systems can be designed with many different couplings. As an example, qubits can be coupled by Josephson coupling. Such coupling is represented in the Hamiltonian that describes the coupled qubits by a σZi{circle around (X)}σZj term, where the “{circle around (X)}” denotes the tensor product. This two qubit term acts on the tensor product of the two states of the ith and jth qubit, having 2*2=4 components and thus is represented by a four dimensional vector. The interaction term can be used to generate the CPHASE gate. In the present basis the interaction term reads:
            σ      Z        ⊗          σ      Z        =      (                            1                          0                          0                          0                                      0                                      -            1                                    0                          0                                      0                          0                                      -            1                                    0                                      0                          0                          0                          1                      )  
Hamiltonians. The Hamiltonian describes the dynamics of a quantum computer. The Hamiltonian can include one and two qubit terms. One qubit operations include σX, representing transitions from one quantum state to the other, for example, by tunneling between basis states. The one qubit term σZ, represents the bias of the qubit, caused by the difference between the energies of the two quantum states. Such bias can be caused in many different ways, including an external magnetic field.
If the system of quantum states, e.g. the basis of the qubit, is chosen differently, then the Pauli operators are represented by a different set of matrices. With respect to superconducting qubits, various choices of the quantum states are discussed in Makhlin et al., 2001, Reviews of Modern Physics 73, pp. 357-400, which is hereby incorporated by reference in its entirety. These choices include representing the quantum states of the qubit according to the charge or the phase of the qubit.
Using the Hamiltonian terms, such as the single qubit terms σX, σY, and σZ and the two qubit term σZi{circle around (X)}σZj as defined above, the Hamiltonian of a quantum computer can be constructed. The Hamiltonian of a quantum computer is a series of Hamiltonian terms, indexed for each qubit or qubit pair, which may have time varying coefficients that represent the strength of the Hamiltonian term. See Nielsen and Chuang, 2000, Quantum Computation and Information Processing, Cambridge University Press, which is hereby incorporated by reference in its entirety.
Universal quantum computation. To make a practical design for a quantum computer, it is believed that one must specify how to decompose any valid quantum computation into a sequence of elementary 1- and 2-qubit quantum gates that can be realized in physical hardware that is feasible to fabricate. The set of these 1- and 2-qubit gates is arbitrary provided it is universal, i.e., capable of achieving any valid quantum computation by only using gates from this set. A widely accepted method of operating quantum computers is the “standard paradigm” of universal quantum computation. According to the standard paradigm, all operations necessary for a quantum computer can be performed by appropriate application of a set of single qubit gates and one two qubit gate, because these operations generate the full special unitary 2 group, denoted SU(2N), and span the space necessary for quantum computation.
A group G, such as the SU(2N) group, is a set of elements together with a binary operation that satisfy the four fundamental properties of closure, associativity, the identity property, and the inverse property. The operation with respect to which a group is defined is often called the “group operation,” and a set is said to be a group “under” this operation. In other words, elements A, B, C, . . . , with binary operation between A and B denoted AB, form a group when they have the following properties:
(i) closure: if A and B are two elements in G, then the product AB is also in G;
(ii) associativity: the defined multiplication is associative, e.g., for all A, B, C∈G, (AB)C=A(BC);
(iii) identity: there is an identity element I (a.k.a., I, ) such that IA=AI=A for every element A∈G; and
(iv) inverse: there must be an inverse or reciprocal of each element. Therefore, the set must contain an element B=A−1 such that AA−1=A−1A=I for each element of G.
The SU(2N) group satisfies these conditions. The SU(2N) group is a subset of the unitary 2N group (U(2N)). Unitary 2N is a group where the objects are 2 by 2 matrices that are unitary, i.e., UU†=1 or U(UT)*=1, and the operation is matrix multiplication. SU(2N) has the general group element:
      U    =          (                                    a                                b                                                              -                              b                *                                                                        a              *                                          )        ⁢        with |a|2+|b|2=1 and where a and b are complex. For more information on special unitary groups, see Arfken, 1985, Mathematical Methods for Physicists, Third Edition, Academic Press, Inc., San Francisco.
Quantum computers that generate the full SU(2N) group space for N qubits are sometimes referred to as universal quantum computers. In particular, two single qubit gates that are based on two non-commuting Hermitian operators, can generate all one qubit quantum gates. A matrix is Hermitian when A†=A. A matrix B is both Hermitian and Unitary whenBB†=I, andB†=B,hence B=B−1. Two qubit gates can entangle the states of two qubit quantum systems.
A common example of a two qubit gate is the controlled NOT (CNOT) gate. The CNOT gate has two input qubits, known as the control qubit and the target qubit, respectively. The action of the CNOT gate can be described as follows. If the control qubit is set to |0, then the target qubit is left alone. If the control qubit is set to |1, then a NOT gate is applied to the target qubit. Many other classical (e.g. AND) or quantum (e.g. CPHASE) two qubit logic gates can be used. However, it is necessary to modify some classical gates to have two outputs. Alternatively, one can use a discrete set of single qubit operations in addition to an entangling two qubit gate operation to approximate, to any desired accuracy, any quantum gate. An example of a discrete set of logic gates is HADAMARD, PHASE (or s), π/8 (or T), and an entangling gate such as CNOT. See Nielsen and Chuang, 2000, Quantum Computation and Information Processing, Cambridge University Press, which is hereby incorporated by reference in its entirety.
Handling errors in quantum computers. Quantum computers are physical devices that contain error sources, also termed noise, which is generated by undesired physical processes. The early history of classical computing included much effort to remove noise from classical computers, e.g. Hamming codes. These errors can be systemic or random and can affect individual qubits, or the entire quantum computer. Preventive error correction schemes for quantum computing exist. See, for example, U.S. Pat. Nos. 5,768,297, 6,128,764, U.S. patent application Publication 2004/0000666A1, “Encoding and Error Suppression for Superconducting Quantum Computers” to Lidar et al., and U.S. patent application Publication 20030023651 A1 entitled “Quantum computation” to Whaley et al., which are hereby incorporated by reference. Error correction techniques have been experimentally verified. For example, see Ollerenshaw, Lidar, and Kay, 2003, “A Magnetic Resonance Realization of Decoherence-Free Quantum Computation,” arxiv.org: quant-ph/0302175, M. S. Byrd, L.-A. Wu, D. A. Lidar, “Overview of Quantum Error Prevention and Leakage Elimination,” arxiv.org: quant-ph/0402098 (2004), each of which is hereby incorporated by reference.
Many quantum error correction schemes require encoding redundancy, either spatial or temporal. Alternatively they could impose expensive operational constraints. Spatial redundancy is where extra qubits are used to encode the states of one logical qubit into more than one physical qubit, e.g. concatenating a plurality of physical qubits together to form a logical qubit. Temporal redundancy is where extra gates need to be applied during the quantum computation. The use of these extra gates means that the quantum computer must run for a longer time, which may not be possible if this longer time exceeds the coherence time of the quantum computer. Error correction schemes that can impose expensive operational constraints on a quantum computer include schemes like Bang-Bang decoupling methods. These methods require fast pulses, where fast is defined as being faster than the characteristic time of the qubits. The requirement of false pulse indicates that implementation of Bang-Bang decoupling may require expensive equipment.
Given the above background, there is clearly a need in the art for improved methods of quantum computation that have reduced reliance on expensive error correction protocols.